home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 1999 August / SGI Freeware 1999 August.iso / dist / samba.idb / usr / samba / src / source / ubiqx / ubi_StackQueue.h.z / ubi_StackQueue.h
Encoding:
C/C++ Source or Header  |  1998-10-28  |  6.8 KB  |  181 lines
  1. #ifndef ubi_StackQueue_H
  2. #define ubi_StackQueue_H
  3. /* ========================================================================== **
  4.  *                              ubi_StackQueue.h
  5.  *
  6.  *  Copyright (C) 1997 by Christopher R. Hertel
  7.  *
  8.  *  Email: crh@ubiqx.mn.org
  9.  * -------------------------------------------------------------------------- **
  10.  *  This module implements simple queues and stacks using a singly linked
  11.  *  list.
  12.  * -------------------------------------------------------------------------- **
  13.  *
  14.  *  This library is free software; you can redistribute it and/or
  15.  *  modify it under the terms of the GNU Library General Public
  16.  *  License as published by the Free Software Foundation; either
  17.  *  version 2 of the License, or (at your option) any later version.
  18.  *
  19.  *  This library is distributed in the hope that it will be useful,
  20.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  21.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  22.  *  Library General Public License for more details.
  23.  *
  24.  *  You should have received a copy of the GNU Library General Public
  25.  *  License along with this library; if not, write to the Free
  26.  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  27.  *
  28.  * -------------------------------------------------------------------------- **
  29.  *  This module uses a singly-linked list to implement both a queue and a
  30.  *  stack.  For a queue, entries are added at the tail and removed from the
  31.  *  head of the list.  For a stack, the entries are entered and removed from
  32.  *  the head of the list. A traversal of the list will always start at the
  33.  *  head of the list and proceed toward the tail.  This is all mind-numbingly
  34.  *  simple, but I'm surprised by the number of programs out there which
  35.  *  re-implement this a dozen or so times.
  36.  *
  37.  *  Note:  When the list header is initialized, the Tail pointer is set to
  38.  *         point to the Head pointer.  This simplifies the InsTail function
  39.  *         at little or no cost to InsHead or Remove.  The one problem is
  40.  *         that you can't initialize a stack or queue headerby simply zeroing
  41.  *         it out.  One sure way to initialize the header is to call
  42.  *         ubi_sqInit().  Another option would be something like this:
  43.  *
  44.  *         static ubi_sqList MyList = { NULL, (ubi_sqNodePtr)&MyList, 0 };
  45.  *
  46.  *         See ubi_sqInit() and the ubi_sqList structure for more info.
  47.  *
  48.  * -------------------------------------------------------------------------- **
  49.  *
  50.  * Revision 0.1  1997/10/24 02:48:23  crh
  51.  * Initial revision.
  52.  *
  53.  * ========================================================================== **
  54.  */
  55.  
  56. #include <stdlib.h>
  57.  
  58.  
  59. /* ========================================================================== **
  60.  * Typedefs...
  61.  *
  62.  *  ubi_sqNode      - This is the basic node structure.
  63.  *  ubi_sqNodePtr   - Pointer to a node.
  64.  *  ubi_sqList      - This is the stack & queue header structure.
  65.  *  ubi_sqListPtr   - Pointer to a stack & queue header.
  66.  *
  67.  */
  68.  
  69. typedef struct ubi_sqListNode
  70.   {
  71.   struct ubi_sqListNode *Next;
  72.   } ubi_sqNode;
  73.  
  74. typedef ubi_sqNode *ubi_sqNodePtr;
  75.  
  76. typedef struct
  77.   {
  78.   ubi_sqNodePtr Head;
  79.   ubi_sqNodePtr Tail;
  80.   unsigned long count;
  81.   } ubi_sqList;
  82.  
  83. typedef ubi_sqList *ubi_sqListPtr;
  84.  
  85. /* ========================================================================== **
  86.  * Macros...
  87.  * 
  88.  *  ubi_sqEnqueue - Add a new node at the tail of a queue.
  89.  *  ubi_sqDequeue - Remove a node from the head of the queue.
  90.  *  ubi_sqPush    - Add a new node at the head of the queue.
  91.  *  ubi_sqPop     - Remove a node from the head of the queue (same as Dequeue). 
  92.  *  ubi_sqFirst   - Return a pointer to the frontmost node in the queue.
  93.  *  ubi_sqNext    - Given a node, return a pointer to the next node.
  94.  *  ubi_sqLast    - Return a pointer to the last (valid) node in the queue.
  95.  *
  96.  *  Note that all of these provide type casting of the parameters.  The
  97.  *  Enqueue/Dequeue macros are nothing more than nice front-ends to the
  98.  *  Insert and Remove operations.
  99.  *
  100.  */
  101.  
  102. #define ubi_sqEnqueue( L, N ) \
  103.         ubi_sqInsTail( (ubi_sqListPtr)(L), (ubi_sqNodePtr)(N) )
  104.  
  105. #define ubi_sqDequeue( L ) ubi_sqRemove( (ubi_sqListPtr)(L) )
  106.  
  107. #define ubi_sqPush( L, N ) \
  108.         ubi_sqInsHead( (ubi_sqListPtr)(L), (ubi_sqNodePtr)(N) )
  109.  
  110. #define ubi_sqPop ubi_sqDequeue
  111.  
  112. #define ubi_sqFirst( L ) (((ubi_sqListPtr)(L))->Head)
  113.  
  114. #define ubi_sqNext( N )  (((ubi_sqNodePtr)(N))->Next)
  115.  
  116. #define ubi_sqLast( L )  \
  117.     ( (((ubi_sqListPtr)(L))->Head) ? (((ubi_sqListPtr)(L))->Tail) : NULL )
  118.  
  119.  
  120. /* ========================================================================== **
  121.  * Function prototypes...
  122.  */
  123.  
  124. ubi_sqListPtr ubi_sqInit( ubi_sqListPtr ListPtr );
  125.   /* ------------------------------------------------------------------------ **
  126.    * Initialize a stack & queue header.
  127.    *
  128.    *  Input:  ListPtr - A pointer to the list header that is to be
  129.    *                    initialized for use.
  130.    *
  131.    *  Output: A pointer to the initialized list header (i.e., same as
  132.    *          <ListPtr>).
  133.    *
  134.    * ------------------------------------------------------------------------ **
  135.    */
  136.  
  137. ubi_sqNodePtr ubi_sqInsHead( ubi_sqListPtr ListPtr, ubi_sqNodePtr New );
  138.   /* ------------------------------------------------------------------------ **
  139.    * Insert a new node at the head of the list (push).
  140.    *
  141.    *  Input:  ListPtr - A pointer to the stack into which the node is to
  142.    *                    be inserted.
  143.    *          New     - Pointer to the node that is to be pushed onto the
  144.    *                    stack.
  145.    *
  146.    *  Output: A pointer to the node that was added to the list (i.e., same
  147.    *          same as <New>).
  148.    *
  149.    * ------------------------------------------------------------------------ **
  150.    */
  151.  
  152. ubi_sqNodePtr ubi_sqInsTail( ubi_sqListPtr ListPtr, ubi_sqNodePtr New );
  153.   /* ------------------------------------------------------------------------ **
  154.    * Add a new node to the tail of the list (enqueue).
  155.    *
  156.    *  Input:  ListPtr - A pointer to the queue into which the node is to
  157.    *                    be inserted.
  158.    *          New     - Pointer to the node that is to be enqueued.
  159.    *
  160.    *  Output: A pointer to the node that was inserted into the queue (i.e.,
  161.    *          the same as <New>).
  162.    *
  163.    * ------------------------------------------------------------------------ **
  164.    */
  165.  
  166. ubi_sqNodePtr ubi_sqRemove( ubi_sqListPtr ListPtr );
  167.   /* ------------------------------------------------------------------------ **
  168.    * Remove the frontmost entry from the queue, or topmost entry from the
  169.    * stack.
  170.    *
  171.    *  Input:  ListPtr - A pointer to the list from which the node is to be
  172.    *                     removed.
  173.    *
  174.    *  Output: A pointer to the node that was removed.
  175.    *
  176.    * ------------------------------------------------------------------------ **
  177.    */
  178.  
  179. /* ================================ The End ================================= */
  180. #endif /* ubi_StackQueue_H */
  181.